package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/20.<br><br>
 *
 * 验证二叉搜索树
 */
public class Topic98 {
    public static void main(String[] args) {
        Topic98 instance = new Topic98();

        List<Integer> list = Arrays.asList(2,1,3);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.isValidBST(root));

        list = Arrays.asList(5,1,4,null,null,3,6);
        root = Util.createTree(list);
        System.out.println(instance.isValidBST(root));

        list = Arrays.asList(2, 2, 2);
        root = Util.createTree(list);
        System.out.println(instance.isValidBST(root));

        list = Arrays.asList(5,4,6,null,null,3,7);
        root = Util.createTree(list);
        System.out.println(instance.isValidBST(root));

        list = Arrays.asList(2147483647);
        root = Util.createTree(list);
        System.out.println(instance.isValidBST(root));
    }

    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }

        return isValidBST(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    private boolean isValidBST(TreeNode root, long max, long min) {
        if(root == null) {
            return true;
        }

        if(root.val >= max || root.val <= min) {
            return false;
        }

        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }

    public boolean isValidBST2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return postTravel(root, list);
    }

    private boolean postTravel(TreeNode root, List<Integer> result) {
        if(root == null) {
            return true;
        }

        boolean leftResult = postTravel(root.left, result);
        if(result.size() > 0 && root.val <= result.get(result.size() - 1)) {
            return false;
        }
        result.add(root.val);
        boolean rightResult = postTravel(root.right, result);
        return leftResult && rightResult;
    }
}
